Computer operating environments, such as the Java Virtual Machine (JVM), typically provide a mechanism for applications to store “objects” of data. Often, the operating environment dynamically allocates a section of memory for utilization by the application into which the application places its objects. In the course of its execution, an application may no longer require an object, allowing the object's location in memory to be reclaimed for storing other objects. This process of reclamation is popularly known as garbage collection (GC).
Garbage collectors from the mark-sweep family suffer from memory fragmentation, which refers to the creation of relatively small holes of unused space between objects. To reduce fragmentation the GC may compact memory by reducing the space between objects and thus create chunks of larger free space, making allocation more efficient, and practically reducing the memory footprint of the application. During compaction, “fixup” of object memory addresses is typically performed to keep track of each object's new location for future reference.
Unfortunately, compaction algorithms tend to require large amounts of auxiliary data structures, such as forwarding references or break tables. Moreover when searching for a previously stored objects, forwarding references may require additional auxiliary memory accesses.